﻿namespace KinonekoSoftware.Extensions.Collections.BST
{
    partial class BinaryTreeCollection<TKey, TValue>
    {

        public void Add(TValue content)
        {
            if (content is null)
            {
                return;
            }

            if (Root is null)
            {
                Root = new Node
                {
                    Key    = _selector( content),
                    Value  = content,
                    Height = 1,
                };

                _height = 1;
                _count++;
                _version++;
                return;
            }

            AddImpl(Root, new Node
            {
                Key    = _selector( content),
                Value  = content,
                Height = 1,
            });
        }

        protected void AddImpl(Node parent, Node node, bool rebalance = true)
        {
            var result = Comparer<TKey>.Default.Compare(parent.Key, node.Key);

            if (result < 0)
            {
                //
                // 如果需要放右边，且右边为空，则放当前位置
                if (parent.Right is null)
                {
                    parent.Right = node;
                    node.Parent  = parent;
                    node.Height  = (byte)(parent.Height + 1);
                    _height      = Math.Max(_height, node.Height);


                    _count++;
                    _version++;
                }
                else
                {
                    AddImpl(parent.Right, node, rebalance);
                }

            }
            else if (result > 0)
            {
                if (parent.Left is null)
                {
                    parent.Left = node;
                    node.Parent = parent;
                    node.Height = (byte)(parent.Height + 1);
                    _height     = Math.Max(_height, node.Height);

                    _count++;
                    _version++;
                }
                else
                {
                    AddImpl(parent.Left, node, rebalance);
                }
            }
            else
            {
                if (!ReferenceEquals(parent.Value, node.Value))
                {
                    var oldValue = parent.Value;
                    var newValue = node.Value;
                    //
                    // 等价不作处理
                    DuplicatedWhenInsertValue?.Invoke(parent, oldValue, newValue);
                }
            }

            if (rebalance)
            {
                parent.Rebalance();
            }
        }

        /// <summary>Inserts an item to the <see cref="T:System.Collections.Generic.IList`1" /> at the specified index.</summary>
        /// <param name="index">The zero-based index at which <paramref name="item" /> should be inserted.</param>
        /// <param name="item">The object to insert into the <see cref="T:System.Collections.Generic.IList`1" />.</param>
        /// <exception cref="T:System.ArgumentOutOfRangeException">
        /// <paramref name="index" /> is not a valid index in the <see cref="T:System.Collections.Generic.IList`1" />.</exception>
        /// <exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.IList`1" /> is read-only.</exception>
        public void Insert(int index, TValue item)
        {

        }
    }
}